#include <iostream>
#include <string>
#include <vector>
#include <cstdio>


#define MAX_HUFF_DEPTH 16


struct HuffTreeNode {


    HuffTreeNode():c(0),path_str(""),left(nullptr),right(nullptr),next(nullptr)
    {}

    HuffTreeNode(int c_, 
                const std::string &str, 
                struct HuffTreeNode *l,
                struct HuffTreeNode *r,
                struct HuffTreeNode *n):c(c_),path_str(str),left(l),right(r),next(n)
    {

    }
    void bfs() const {
        const HuffTreeNode *leftMost = left;

        for ( ; leftMost != nullptr; ) {
            const HuffTreeNode *node = leftMost;
            for (; node->isLegalNode() ;node = node->next) {
                    printf("%c ", node->c);
            }
            if (node != leftMost)
                printf("\n");
            leftMost = node->left;
        }
    
    }

    ~HuffTreeNode() {
        delete left;
        delete right;
    }
    bool isLegalNode() const {
        return left == nullptr &&  right == nullptr && c != 0;
    }



    int c;
    std::string path_str;
    struct HuffTreeNode *left;
    struct HuffTreeNode *right;
    struct HuffTreeNode *next;
};
bool checkSymbol(const std::vector<int> &symbolCnt, const std::vector<int> &symbol)
{
    int symsCntSz = symbolCnt.size(); 
    if ( symsCntSz != MAX_HUFF_DEPTH)
        return false;

    int tot = 0;
    for (int i = 0;i < MAX_HUFF_DEPTH; i++) {
        tot += symbolCnt[i];
    }
    return symbol.size() == tot;
}

void dumpSymbol(const std::vector<int> &symbolCnt, const std::vector<int> &symbols)
{
    if ( !checkSymbol( symbolCnt, symbols)) {
        printf("symbols error!\n");
        exit(EXIT_FAILURE);
    }

    
    int symbolNum = symbols.size();
    int cur = 0;
    for (int i = 0;i < MAX_HUFF_DEPTH;++i) {
        if ( !symbolCnt[i] ) 
            continue;

            for (int j = 0;j < symbolCnt[i]; j++, cur++) {
                if (cur >= symbolNum) {
                    printf("symbols not same as symbolCnt\n");
                    break;
                }

                if (0 == j) 
                    printf("cnt of depth %d: ", i + 1);
                
                printf(" %c", symbols[cur]);
                if (j == symbolCnt[i] - 1)
                    printf("\n");
            }
            if (cur >= symbolNum)
                break;
            
    }
}


void GenSon(HuffTreeNode *rt) 
{
    rt->left  = new HuffTreeNode();
    rt->right = new HuffTreeNode();

    rt->left->path_str = rt->path_str + '0';
    rt->right->path_str = rt->path_str + '1';

    rt->left->next = rt->right;
}


//  给定HuffMan树每层的叶子节点数，
//  和HuffMan树的层序遍历结果
//  要求重构HuffMan树

int main(int argc, char *argv[])
{

    std::vector<int> symbolCnt = 
                                 { 0, 1, 5, 1, 
                                   1, 1, 1, 1, 
                                   1, 0, 0, 0, 
                                   0, 0, 0, 0
                                };
    std::vector<int> symbols   = { 'a', 'b', 'c', 'd', 
                                   'e', 'f', 'g', 'h', 
                                  'i', 'j', 'k', 'l'};


    HuffTreeNode *root = new HuffTreeNode();
    GenSon(root);

    

    HuffTreeNode *leftMost = root->left;
    int cur = 0;
    for (int i = 0;i < MAX_HUFF_DEPTH; i++) {

        int symCnti = symbolCnt[i];
        for (int j = 0; j < symCnti; j++, cur++) {
            if (leftMost == nullptr) {
                printf("symbol ilegal!\n");
                exit(EXIT_FAILURE);
            }
            else {

                printf("add symbol %c at: %s\n", symbols[cur], leftMost->path_str.c_str());
                leftMost->c = symbols[cur];
                leftMost = leftMost->next;
            }
        } 
        
        HuffTreeNode *node = leftMost;
        HuffTreeNode *nextPre = nullptr;
        
        for (;node != nullptr; node = node->next) {
            GenSon(node);
            if (nextPre)
                nextPre->next = node->left;
            nextPre = node->right;
        }
        leftMost = leftMost->left;
    }

    root->bfs();

    delete root;

    return 0;
}

// 1. 创建空节点
// 2. 加入两个儿子节点
// 3. 设置最左边节点
// 4. 遍历高度节点表
//     4.1 该高度有节点
//         a) leftMost为空，说明这个节点高度表不能生成一颗HuffMan树，返回错误。
//         b) leftMost不为空，将leftMost指向节点设置为对应的字符，更新leftMost为它的右边节点。
//     4.2 该高度没有节点
//         a) 保存leftMost节点
//         b) 设置nextPre节点
//         c) 取curNode为leftMost，从左往右遍历
//             （1）curNode生成两个孩子节点
//             （2）将nextPre节点指向curNode的左儿子
//             （3）更新nextPre为curNode的右儿子
//     4.3 更新leftMost为leftMost->left